package com.shm.leetcode;

/**
 * 959. 由斜杠划分区域
 * 在由 1 x 1 方格组成的 N x N 网格 grid 中，每个 1 x 1 方块由 /、\ 或空格构成。这些字符会将方块划分为一些共边的区域。
 *
 * （请注意，反斜杠字符是转义的，因此 \ 用 "\\" 表示。）。
 *
 * 返回区域的数目。
 *
 *
 *
 * 示例 1：
 *
 * 输入：
 * [
 *   " /",
 *   "/ "
 * ]
 * 输出：2
 * 解释：2x2 网格如下：
 *
 * 示例 2：
 *
 * 输入：
 * [
 *   " /",
 *   "  "
 * ]
 * 输出：1
 * 解释：2x2 网格如下：
 *
 * 示例 3：
 *
 * 输入：
 * [
 *   "\\/",
 *   "/\\"
 * ]
 * 输出：4
 * 解释：（回想一下，因为 \ 字符是转义的，所以 "\\/" 表示 \/，而 "/\\" 表示 /\。）
 * 2x2 网格如下：
 *
 * 示例 4：
 *
 * 输入：
 * [
 *   "/\\",
 *   "\\/"
 * ]
 * 输出：5
 * 解释：（回想一下，因为 \ 字符是转义的，所以 "/\\" 表示 /\，而 "\\/" 表示 \/。）
 * 2x2 网格如下：
 *
 * 示例 5：
 *
 * 输入：
 * [
 *   "//",
 *   "/ "
 * ]
 * 输出：3
 * 解释：2x2 网格如下：
 *
 *
 *
 * 提示：
 *
 * 1 <= grid.length == grid[0].length <= 30
 * grid[i][j] 是 '/'、'\'、或 ' '。
 *
 * @author SHM
 */
public class RegionsBySlashes {
    /**
     * 这是一个关于连通性的问题，让我们求解连通分量的个数，解决这个问题没有特别的技巧，根据题意 画图分析、稍微细心一点就可以通过系统测评。
     *
     * 可以用深度优先遍历（Depth First Search）、广度优先遍历（Breadth First Search）和并查集（Disjoint Sets），由于只要求计算结果，不要求给出具体的连通信息，可以使用并查集。
     *
     * 方法：并查集
     * 「斜杠」、「反斜杠」把单元格拆分成的 2 个三角形的形态，在做合并的时候需要分类讨论。根据「斜杠」、「反斜杠」分割的特点，我们把一个单元格分割成逻辑上的 4 个部分。如下图所示：
     *
     *
     *
     * 我们须要遍历一次输入的二维网格 grid，在 单元格内 和 单元格间 进行合并。
     *
     * 单元格内：
     *
     * 如果是空格：合并 0、1、2、3；
     * 如果是斜杠：合并 0、3，合并 1、2；
     * 如果是反斜杠：合并 0、1，合并 2、3。
     * 单元格间：
     *
     * 我们选择在遍历 grid 的每一个单元格的时候，分别向右、向下尝试合并。
     *
     *
     *
     * 向右：合并 1 （当前单元格）和 3（当前单元格右边 1 列的单元格），上图中红色部分；
     * 向下：合并 2 （当前单元格）和 0（当前单元格下边 1 列的单元格），上图中蓝色部分。
     * 并查集里连通分量的个数就是题目要求的区域的个数。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(N^2 \log N)O(N
     * 2
     *  logN)，其中 NN 是网格的长度，O(N^2 \log N^2) = O(2N^2 \log N)O(N
     * 2
     *  logN
     * 2
     *  )=O(2N
     * 2
     *  logN)；
     * 空间复杂度：O(N^2)O(N
     * 2
     *  )。
     *
     * 作者：LeetCode
     * 链接：https://leetcode-cn.com/problems/regions-cut-by-slashes/solution/you-xie-gang-hua-fen-qu-yu-by-leetcode-67xb/
     * @param grid
     * @return
     */
    public int regionsBySlashes(String[] grid) {
        int n = grid.length;
        int size = 4*n*n;

        UnionFind uf= new UnionFind(size);
        for (int i = 0; i < n; i++) {
            char[] row = grid[i].toCharArray();
            for (int j = 0; j < n; j++) {
                char c = row[j];
                int index = 4*(i*n+j);
                if(c=='/'){
                    uf.union(index,index+3);
                    uf.union(index+1,index+2);
                }else if(c=='\\'){
                    uf.union(index,index+1);
                    uf.union(index+2,index+3);
                }else {
                    uf.union(index,index+1);
                    uf.union(index+1,index+2);
                    uf.union(index+2,index+3);
                }

                if(j+1<n){
                    uf.union(index+1,4*(i*n+j+1)+3);
                }
                if(i+1<n){
                    uf.union(index+2,4*((i+1)*n+j));
                }
            }
        }
        return uf.getCount();
    }

    class UnionFind{
        int[] parent;
        int count;

        UnionFind(int n){
            parent = new int[n];
            count = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        int find(int x){
//            if(x!=parent[x]){
//                parent[x] = find(parent[x]);
//            }
//            return parent[x];

            while (x!=parent[x]){
                parent[x] = parent[parent[x]];
                x=parent[x];
            }
            return x;
        }

        void union(int x,int y){
            int newX = find(x);
            int newY = find(y);

            if (newX==newY){
                return;
            }

            parent[newY] = newX;
            count--;
        }

        int getCount(){
            return count;
        }
    }

}
